一.群
1.群的定义
对于一个集合 S 和定义在这个集合上的二元运算 ∗ , 满足:
-
封闭性。 ∀a∈S,b∈S ,a∗b∈S
-
结合律。 a∗b∗c=a∗(b∗c)
-
单位元。 ∃ϵ∈S , a∗ϵ=ϵ∗a=a
-
逆元。 ∀a∈S , ∃b∈S , a∗b=ϵ , 记作 a′
那么称 (S,∗) 为一个群。
值得注意的是,一个群的单位元和逆元都是唯一的。
2.子群
若 G(S,∗) 为一个群,若 T⊆S ,且 H(T,∗) 也为一个群,那么称 H 为 G 的子群,记作 H≤G
3.陪集
左陪集:若群 H 为群 G 的一个子群,且对于 g∈G,gH={gh∣h∈H}。
同样可以定义右陪集。
注意陪集可能不包含单位元,不一定是群。
陪集的性质:
- ∣H∣=∣gH∣
- g∈gH
- gH=H⇔g∈H
- aH=bH⇔a∗b−1∈H
- aH=BH⇒aH⋂bH=∅
- g∈G⋃gH=G
二.拉格朗日定理
[G:H]: G 中 H 不同陪集的数量
G / H : G 中所有 H 的左陪集
有:
∣H∣×[G:H]=∣G∣
证明:由陪集的性质 1、5、6 显然。
三.置换群
1.置换
对于集合 S={a1,a2…an} , 一个置换 f 可表示为:
f=(a1,a2,…,anap1,ap2,…,apn)
p 为 1∼n 的排列,意义为将 ai 映射为 api。
f=(ap1,ap2,…,apnaq1,aq2,…,aqn),g=(a1,a2,…,anap1,ap2,…,apn)
f×g=f(g(x))=(a1,a2,…,anaq1,aq2,…,aqn)
称为置换的乘法。
2.循环置换
一种特殊的置换,其中:
f=(a1,a2,…,an)=(a1,a2,…,ana2,a3,…,a1)
任意一个置换都可以表示为若干不相交的循环置换的乘积,例如
(a1,a2,a3,a4,a5a3,a1,a2,a5,a4)=(a1,a3,a2)×(a4,a5)
将一个置换 f 拆分的循环置换个数记为 c(f)
3.置换群
若 S 包含所有的 n! 个不同 n 元置换,G(S,×) 为一个群,证明如下:
- 封闭性。 两个 n 元置换的乘积仍为 n 元置换,包含于 S。
- 结合律。置换的乘法有结合律。
- 单位元。置换 (a1,a2,…,ana1,a2,…,an),也称恒等置换。
- 逆元。上下两行交换即可。
G 的子群称作置换群。
四.Burnsied 引理 和 Pólya 定理
1.轨道稳定子定理
对于作用在集合 X 上的群 G 和集合 X 的一个元素 x
x 的轨道:G(x)={g(x)∣g∈G}
x 的稳定子:Gx={g∈G∣g(x)=x}
这里 g(x) 为群作用的函数,例如上文提到的置换。
-
Gx 为 G 的子群。
证明:
- 封闭性。 f(x)=x,g(x)=x,f×g=f(g(x))=x,所以 f×g∈Gx
- 结合律。显然。
- 单位元。ϵ(x)=x,所以 ϵ∈Gx
- 逆元。∀g∈G,因为 g×g′=ϵ , g(x)=ϵ(x)=x,所以 g′(x)=x,g′(x)∈G
-
∣G(x)∣=[G:Gx]
证明:
对于 f(x)=g(x) , f×g−1=ϵ
若有两个 f(x)=g(x),f×g−1=x=ϵ(x) ,所以 f×g−1∈Gx , ⇒fGx=gGx , 反之亦然。
即不同的 g 对应不同的陪集。
所以对于 G(x) 中的 g , 构造对应陪集为 gGx。
感觉在伪证。
轨道稳定子定理:
∣G(x)∣×∣Gx∣=∣G∣
证明:
因为 Gx 为 G 的子群,由拉格朗日定理得:
∣Gx∣×[G:Gx]=∣G∣
由性质2得:
∣Gx∣×∣G(x)∣=∣G∣
证毕。
2.Burnside 引理
若一个置换群 G 作用于 X , X/G 表示在群 G 作用下 X 的所有等价类的集合。(注意每个等价类也是一个集合,若两个元素在 G 作用下可以转化则属于同一个等价类)
Xg 表示在 g 的作用下不变的 X 中元素的集合。
那么有:
∣X/G∣=∣G∣1g∈G∑∣Xg∣
证明:
g∈G∑∣Xg∣=x∈X∑∣Gx∣=x∈X∑∣G(x)∣∣G∣=∣G∣x∈X∑∣G(x)∣1=∣G∣Y∈X/G∑x∈Y∑∣G(x)∣1=∣G∣Y∈X/G∑x∈Y∑∣Y∣1=∣G∣Y∈X/G∑1=∣G∣∣X/G∣
即:
∣X/G∣=∣G∣1g∈G∑∣Xg∣
可以参考 oi-wiki 的例子。
3.Pólya 定理
∣X/G∣=∣G∣1g∈G∑mc(g)
证明:
由 burnside 引理发现,在 g 作用下的不动点的充要条件是每一个循环置换里元素同色。
那么式子就很显然了。
五.例题
首先置换群 G 包含的元素分别为: 旋转 1 个点,旋转 2 个点...旋转 n 个点
不难发现,旋转 k 个点的 c(g)=gcd(n,k),原因如下:
所有循环置换所包含的元素个数相同,均为 klcm(n,k)。(旋转次数/旋转步长)
那么循环置换的个数便为 klcm(n,k)n=gcd(n,k)
由 polya 定理得:
∣X/G∣=n1i=1∑nngcd(i,n)
化简可得:
∣X/G∣=n1d∣n∑ndφ(dn)
直接计算即可,复杂度 O(n43)
#include <cstdio>
const int Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return 1ll * x * Inv( y ) % Mod; }
int phi( int n ) {
int Ans = n;
for( int i = 2 ; i * i <= n ; i ++ )
if( n % i == 0 ) {
Ans = Ans / i * ( i - 1 );
while( n % i == 0 ) n /= i;
}
if( n > 1 ) Ans = Ans / n * ( n - 1 );
return Ans;
}
int T , n;
int main( ) {
scanf("%d",&T);
while( T -- ) {
scanf("%d",&n);
int Ans = 0;
for( int i = 1 ; i * i <= n ; i ++ )
if( n % i == 0 ) {
Ans = Add( Ans , Mul( Quick_pow( n , i ) , phi( n / i ) ) );
if( i * i != n )
Ans = Add( Ans , Mul( Quick_pow( n , n / i ) , phi( i ) ) );
}
printf("%d\n", Div( Ans , n ) );
}
return 0;
}